package main.leetcode.clockin.March;

import main.datastruc.ListNode;

/**
 * 206.反转链表
 *
 * <p>反转一个单链表。
 *
 * <p>示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day2 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode pre = head;
        for (int i = 2; i < 6; i++) {
            pre.next = new ListNode(i);
            pre = pre.next;
        }
        System.out.println(new day2().reverseList2(head));
    }

    // 迭代
    public ListNode reverseList1(ListNode head) {
        if (head == null) return null;
        ListNode newHead = null;
        ListNode pre = head;
        ListNode node;
        while (pre != null) {
            node = pre.next;
            pre.next = newHead;
            newHead = pre;
            pre = node;
        }
        return newHead;
    }
    // 迭代
    public ListNode reverseList2(ListNode head) {
        if (head == null) return null;
        ListNode newHead = null;
        ListNode node;
        while (head != null) {
            node = head.next;
            head.next = newHead;
            newHead = head;
            head = node;
        }
        return newHead;
    }
    // 递归
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next); // 找到尾结点
        head.next.next = head;
        head.next = null;
        return p;
    }
}
